#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#define MAX_SIZE 100

bool Check(int N, int P[], int A[]);
void Insert_sort(int i, int Num[]);
void Heap_sort(int A[], int N, int start);
void PercDown(int A[], int p, int N);
int main()
{
    int Sort_N[MAX_SIZE], Num[MAX_SIZE], Partial_N[MAX_SIZE];
    int N, len;
    bool flag = false; // 1. check if Insert sort; 2. check if finished sort

    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &Num[i]);
        Sort_N[i] = Num[i];
    }
        
    for (int i = 0; i < N; i++)
        scanf("%d", &Partial_N[i]);

    //Check for Insertion
    for (int i = 1; i < N; i++)
    {
        Insert_sort(i, Num);
        flag = Check(N, Partial_N, Num);
        if (flag)
        {
            Insert_sort(++i, Num);
            break;
        }
            
    }
    if(!flag)
    {

        // From slides 9.3 堆排序
        int i;
        // build max heap with binary tree
        for (i = N / 2 - 1; i >= 0; i--)
            PercDown(Sort_N, i, N);

        //definitely heap
        for (len = N - 1; len > 0; len--)
        {
            flag = Check(N, Partial_N, Sort_N);
            Heap_sort(Sort_N, N, len);
            if(flag)
                break;
            
        }
        printf("Heap Sort\n");
        printf("%d", Sort_N[0]);
        for (int i = 1; i < N;i++)
            printf(" %d", Sort_N[i]);
    }
    else
    {
        printf("Insertion Sort\n");
        printf("%d", Num[0]);
        for (int i = 1; i < N;i++)
        {
            printf(" %d", Num[i]);
        }
    }

    return 0;
}

bool Check(int N, int P[], int A[])
{
    for (int i = 0; i < N;i++)
    {
        if(P[i]!=A[i])
            return false;
    }
    return true;
}
void PercDown(int A[], int p, int N)
{
    // From slides 9.3 堆排序
    /* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
    int Parent, Child;
    int X;
    X = A[p];
    for (Parent = p; Parent * 2 + 1 < N; Parent = Child)
    {
        Child = Parent * 2 + 1;
        //首先确保child下标没超，然后对比哪个更大
        if ((Child != N - 1) && (A[Child] < A[Child + 1]))
            Child++;
        if (X >= A[Child])
            break; //找到了位置
        else
            A[Parent] = A[Child];//否则进入下一层继续看
    }
    A[Parent] = X;
}
void Heap_sort(int A[], int N, int start)
{
    //swap max value and delete
    int temp = A[0];
    A[0] = A[start];
    A[start] = temp;
    PercDown( A, 0, start );
}
void Insert_sort(int i, int Num[])
{
    int temp;
    for (int j = 0; j < i; j++)
    {
        if(Num[j]>Num[i])
        {
            temp = Num[i];
            Num[i] = Num[j];
            Num[j] = temp;
        }
    }
}